import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/6 18:22
 * @description 单调栈，要使最后的代价最小，类似于哈夫曼树，那么我们需要将较小的树放在底部，构成非叶子节点的值才越小。
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int mctFromLeafValues(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        stack.push(Integer.MAX_VALUE);
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            // 栈顶维护最小值，当元素大于栈顶元素时，弹出栈顶作为最小的左节点，前一个元素和当前元素，取较小的作为右节点
            while (arr[i] >= stack.peek()) {
                ans += stack.pop() * Math.min(stack.peek(), arr[i]);
            }
            stack.push(arr[i]);
        }
        // 原数组遍历完，栈中还有多余数据，
        while (stack.size() > 2) {
            ans += stack.pop() * stack.peek();
        }
        return ans;
    }
}
